Non%2DSparse Regularization and Efficient Training with Multiple Kernels

Approximate Tree Kernels.
Editor: John Shawe-Taylor Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.
Efficient Classification of Images with Taxonomies.

Active learning for network intrusion detection.

Feature Selection for Density Level%2DSets.

Automatic feature selection for anomaly detection.

Exact and Approximate Inference for Annotating Graphs with Structural SVMs.

Transductive support vector machines for structured variables.
We study the problem of learning kernel machines transductively for structured output variables. Transductive learning can be reduced to combinatorial optimization problems over all possible labelings of the unlabeled data. In order to scale transductive learning to structured variables, we transform the corresponding non-convex, combinatorial, constrained optimization problems into continuous, unconstrained optimization problems. The discrete optimization parameters are eliminated and the resulting differentiable problems can be optimized efficiently. We study the effectiveness of the generalized TSVM on multiclass classification and labelsequence learning problems empirically. 1.
Supervised clustering of streaming data for email batch detection.
We address the problem of detecting batches of emails that have been created according to the same template. This problem is motivated by the desire to filter spam more effectively by exploiting collective information about entire batches of jointly generated messages. The application matches the problem setting of supervised clustering, because examples of correct clusterings can be collected. Known decoding procedures for supervised clustering are cubic in the number of instances. When decisions cannot be reconsidered once they have been made – owing to the streaming nature of the data – then the decoding problem can be solved in linear time. We devise a sequential decoding procedure and derive the corresponding optimization problem of supervised clustering. We study the impact of collective attributes of email batches on the effectiveness of recognizing spam emails. 1.
Support Vector Machines for Collective Inference.

Efficient co%2Dregularised least squares regression.
In many applications, unlabelled examples are inexpensive and easy to obtain. Semisupervised approaches try to utilise such examples to reduce the predictive error. In this paper, we investigate a semi-supervised least squares regression algorithm based on the co-learning approach. Similar to other semisupervised algorithms, our base algorithm has cubic runtime complexity in the number of unlabelled examples. To be able to handle larger sets of unlabelled examples, we devise a semi-parametric variant that scales linearly in the number of unlabelled examples. Experiments show a significant error reduction by co-regularisation and a large runtime improvement for the semi-parametric approximation. Last but not least, we propose a distributed procedure that can be applied without collecting all data at a single site. 1.
Semi%2Dsupervised learning for structured output variables.
The problem of learning a mapping between input and structured, interdependent output variables covers sequential, spatial, and relational learning as well as predicting recursive structures. Joint feature representations of the input and output variables have paved the way to leveraging discriminative learners such as SVMs to this class of problems. We address the problem of semi-supervised learning in joint input output spaces. The cotraining approach is based on the principle of maximizing the consensus among multiple independent hypotheses; we develop this principle into a semi-supervised support vector learning algorithm for joint input output spaces and arbitrary loss functions. Experiments investigate the benefit of semisupervised structured models in terms of accuracy and F1 score. 1.
Multi%2Dview Discriminative Sequential Learning.
1 Introduction The problem of labeling observation sequences has applications that range fromlanguage processing tasks such as named entity recognition, part-of-speech tagging, and information extraction to biological tasks in which the instances areoften DNA strings. Traditionally, sequence models such as the hidden Markov model and variants thereof have been applied to the label sequence learningproblem. Learning procedures for generative models adjust the parameters such that the joint likelihood of training observations and label sequences is maxi-mized. By contrast, from the application point of view the true benefit of a label sequence predictor corresponds to its ability to find the correct label sequencegiven an observation sequence.
Multi%2DView Hidden Markov Perceptrons.
Discriminative learning techniques for sequential  data have proven to be more effective than  generative models for named entity recognition,  information extraction, and other tasks of discrimination.
Systematic feature evaluation for gene name recognition.
Background: The goal of the first BioCreAtIvE challenge (Critical Assessment of Information Extraction in Biology) was to provide a set of common evaluation tasks to assess the state of the art for text mining applied to biological problems. The results were presented in a workshop held in Granada, Spain March 28–31, 2004. The articles collected in this BMC Bioinformatics supplement entitled &amp;quot;A critical assessment of text mining methods in molecular biology &amp;quot; describe the BioCreAtIvE tasks, systems, results and their independent evaluation. Results: BioCreAtIvE focused on two tasks. The first dealt with extraction of gene or protein names from text, and their mapping into standardized gene identifiers for three model organism databases (fly, mouse, yeast). The second task addressed issues of functional annotation, requiring systems to identify specific text passages that supported Gene Ontology annotations for specific proteins, given full text articles. Conclusion: The first BioCreAtIvE assessment achieved a high level of international participation (27 groups from 10 countries). The assessment provided state-of-the-art performance results for a basic task (gene name finding and normalization), where the best systems achieved a balanced 80%
LWA 2004 Lernen %2D Wissensentdeckung %2D Adaptivit%E4t

LWA 2004 Lernen %2D Wissensentdeckung %2D Adaptivit%E4t

Co%2DEM support vector learning.
Multi-view algorithms, such as co-training  and co-EM, utilize unlabeled data when the  available attributes can be split into independent  and compatible subsets. Co-EM  outperforms co-training for many problems,  but it requires the underlying learner to estimate  class probabilities, and to learn from  probabilistically labeled data. Therefore, coEM  has so far only been studied with naive  Bayesian learners. We cast linear classifiers  into a probabilistic framework and develop  a co-EM version of the Support Vector Machine.
Multi%2DView Lernen.

Support Vector Machines with Example Dependent Costs.
 Classical learning algorithms from the fields of artificial neural networks and machine learning, typically, do not take any costs into account or allow only costs depending on the classes of the examples that are used for learning. As an extension of class dependent costs, we consider costs that are example, i.e. feature and class dependent. We present a natural cost-sensitive extension of the support vector machine (SVM) and discuss its relation to the Bayes rule. We also derive an approach for including example dependent costs into an arbitrary cost-insensitive learning algorithm by sampling according to modified probability distributions.
Perceptron and SVM learning with generalized cost models.
1 Learning algorithms from the fields of artificial neural networks and machine learning, typically, do not take any costs into account or allow only costs depending on the classes of the examples that are used for learning. As an extension of class dependent costs, we consider costs that are example, i.e. feature and class dependent. We derive a costsensitive perceptron learning rule for non-separable classes, that can be extended to multi-modal classes (DIPOL) and present a natural cost-sensitive extension of the support vector machine (SVM). We also derive an approach for including example dependent costs into an arbitrary cost-insensitive learning algorithm by sampling according to modified probability distributions. 2 1
Support Vector Machines with Example Dependent Costs.
 Classical learning algorithms from the fields of artificial neural networks and machine learning, typically, do not take any costs into account or allow only costs depending on the classes of the examples that are used for learning. As an extension of class dependent costs, we consider costs that are example, i.e. feature and class dependent. We present a natural cost-sensitive extension of the support vector machine (SVM) and discuss its relation to the Bayes rule. We also derive an approach for including example dependent costs into an arbitrary cost-insensitive learning algorithm by sampling according to modified probability distributions.
Learning Linear Classifiers Sensitive to Example Dependent and Noisy Costs.

